package LeetCode;

import java.util.List;

/**
 * 反转链表-给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
 */
public class Num206 {
    public ListNode reverseList(ListNode head) {
        //3.递归
        if(head==null||head.next==null){
            return head;
        }
        ListNode next=head.next;//原先待处理节点的下一个节点
        ListNode newHead=reverseList(head.next);//反转第二个节点后的子链表
       //处理头和第二个节点的关系，将next.next=head;head.next=null[反转步骤]
        next.next=head;
        head.next=null;
        return newHead;
        //2.原地移动
//        if(head==null||head.next==null){
//            return head;
//        }
//        ListNode cur=head;//当前需要反转的节点
//        ListNode prev=null;
//        while(cur!=null){
//            ListNode next=cur.next;//暂存下一个需要处理的节点
//            cur.next=prev;
//            prev=cur;
//            cur=next;
//        }
//      return prev;//cur为空头刚好是prev
        //1.头插法
//        if(head==null||head.next==null){//头插前判断链表是否为空或只有一个节点
//            return head;
//        }
//        //新链表的虚拟头节点
//        ListNode dummyHead=new ListNode(5001);
//        while(head!=null){
//            ListNode node=new ListNode(head.val);
//            //插入节点
//            node.next=dummyHead.next;
//            dummyHead.next=node;
//            //原链表head更新
//            head=head.next;
//        }
//        return dummyHead.next;
    }
}
